package com.cg.leetcode;

import org.junit.Test;

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * 583.两个字符串的删除操作
 *
 * @program: LeetCode->LeetCode_583
 * @description: 583.两个字符串的删除操作
 * @author: cg
 * @create: 2021-09-25 22:49
 **/
public class LeetCode_583 {

    @Test
    public void test583() {
        System.out.println(minDistance("sea", "eat"));
        System.out.println(minDistance("sea", "ate"));
        System.out.println(minDistance("asdasd", "asdefcdd"));
    }

    /**
     * 给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。
     * <p>
     * 示例：
     * 输入: "sea", "eat"
     * 输出: 2
     * 解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"
     * <p>
     * 提示：
     * 1) 给定单词的长度不超过500。
     * 2) 给定单词中的字符只含有小写字母。
     *
     * @param word1
     * @param word2
     * @return
     */
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            char c1 = word1.charAt(i - 1);
            for (int j = 1; j <= n; j++) {
                char c2 = word2.charAt(j - 1);
                if (c1 == c2) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        int lcs = dp[m][n];
        return m - lcs + n - lcs;
    }

}
